package Leetcode;


import java.awt.*;

/**
 * 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 */
public class test21 {


    /**
     * 遍历拼接法
     * @param list1
     * @param list2
     * @return
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
         //判断链表是否为空
        if (list1==null){
            return list2;
        }
        if (list2==null){
            return list1;
        }
        ListNode dummyHrad=new ListNode();
        ListNode fir=dummyHrad;
        //此时两个链表都不为空，遍历并拼接到新链表
        while (list1!=null&&list2!=null){
            //List1小于等于List2时，把List1拼接到新链表上
            if (list1.val<=list2.val){
                fir.next=list1;
                fir=fir.next;
                list1=list1.next;
            } else{
                //List1大于List2时，把List2拼接新链表上
                fir.next=list2;
                fir=fir.next;
                list2=list2.next;
            }
            //当有一个链表为空时，就把另外一个链表的剩下的所有节点都拼接过来
            if (list1==null){
                fir.next=list2;
            }
            if (list2==null){
                fir.next=list1;
            }
            //返回拼接后的链表
        }return dummyHrad.next;
    }

    /**
     * 递归思路
     * @param list1
     * @param list2
     * @return
     */
    public ListNode mergeTwoLists1(ListNode list1, ListNode list2){
        //判断链表是链表为空
        if (list1==null){
            return list2;
        }
        if (list2==null){
            return list1;
        }

        if (list1.val<=list2.val){
            //此时list1.next以及list2交给函数处理，不用管
            list1.next=mergeTwoLists1(list1.next,list2);
            return list1;
        }
        //此时list1>list2,就把list2.next和list1交给函数处理
        list2.next=mergeTwoLists1(list2.next,list1);
        return list2;

    }

}
